package structure;

import java.util.LinkedList;

public class DoubleLinkedList2 {
    private static class Node{
        int val;
        Node prev;
        Node next;

        Node(int val) {
            this.val = val;
        }
    }

    public Node head;
    public Node last;
    private int size;

    // 1.头插法
    public void addFirst(int val) {
        Node node = new Node(val);
        if (head == null) {
            head = last = node;
            size++;
            return;
        }

        head.prev = node;
        node.next = head;
        head = node;
        size++;
    }

    // 2.尾插法
    public void addLast(int val) {
        Node node = new Node(val);
        if (head == null) {
            head = last = node;
            size++;
            return;
        }

        last.next = node;
        node.prev = last;
        last = node;
        size++;
    }

    // 3.插入指定位置
    public void addIndex(int val, int index) {
        if (index < 0 || index > size) {
            return;
        }
        if (index == 0) {
            addFirst(val);
            return;
        }
        if (index == size) {
            addLast(val);
            return;
        }

        // 找到要插入的这个位置的节点
        Node cur = findTheNode(index);
        // prev是cur的前一个节点, 方便后续连接节点
        Node prev = cur.prev;

        Node node = new Node(val);
        node.next = cur;
        cur.prev = node;

        node.prev = prev;
        prev.next = node;
        size++;
    }

    // 4.查找key是否存在
    public boolean contains(int val) {
        Node cur = head;
        while (cur != null) {
            if (cur.val == val) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 5.删除第一个val
    public boolean remove(int val) {
        if (head == null) {
            return false;
        }
        Node cur = head;
        while (cur != null) {
            if (cur.val == val) {
                if (cur == head) {
                    head = head.next;
                    if (head == null) {
                        last = null;
                    }else {
                        head.prev.next = null;
                        head.prev = null;
                    }
                }else if (cur == last) {
                    last = last.prev;
                    last.next = null;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                size--;
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public void removeAll(int val) {
        Node cur = head;
        while (cur != null) {
            if (cur.val == val) {
                if (cur == head) {
                    head = head.next;
                    if (head == null) {
                        last = null;
                    }else {
                        head.prev.next = null;
                        head.prev = null;
                    }
                }else if (cur == last) {
                    last = last.prev;
                    last.next = null;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                size--;
            }
            cur = cur.next;
        }
    }

    public void clear() {
        Node cur = head;
        while (cur != null) {
            Node curNext = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = curNext;
        }
        head = last = null;
        size = 0;
    }

    private Node findTheNode(int index) {
        Node cur = head;
        while (index != 0) {
            index--;
            cur = cur.next;
        }
        return cur;
    }

    public void print() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        DoubleLinkedList2 linkedList2 = new DoubleLinkedList2();
        linkedList2.addLast(1);
        linkedList2.addLast(2);
        linkedList2.addLast(3);
        linkedList2.addLast(3);
        linkedList2.addLast(3);
        linkedList2.addIndex(7,2);
        linkedList2.print();

        linkedList2.remove(1);
        linkedList2.print();
        linkedList2.removeAll(3);
        linkedList2.print();
    }
}
